package search;
//https://leetcode.cn/leetbook/read/illustration-of-algorithm/5874p1/
//https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/description/
public class LCR_172统计目标成绩的出现次数 {
    //二分法
    class Solution {
        public int countTarget(int[] scores, int target) {
            if(scores.length == 0) return 0;
            int i =0, j = scores.length - 1;
            while (i <= j){
                int m = (i + j) / 2;
                if(scores[m] <= target) i = m+1;
                else j = m-1;
            }
            int right = i;
            if(j >= 0 && scores[j] != target) return 0;
            i = 0;
            j = right;
            while (i <= j){
                int m = (i + j) / 2;
                if(scores[m] < target) i = m+1;
                else j = m-1;
            }
            int left = j;
            return right - left - 1;
        }
    }
    //优化
    class Solution2 {
        public int countTarget(int[] scores, int target) {
            if(scores.length == 0) return 0;
            return helper(scores,target) - helper(scores,target-1);
        }
        private int helper(int[] scores, int target){
            int i=0, j = scores.length - 1;
            while (i <= j){
                int m = (i + j) / 2;
                if(scores[m] <= target) i = m+1;
                else j = m-1;
            }
            return i;
        }
    }
    //暴力
    class Solution3 {
        public int countTarget(int[] scores, int target) {
            if(scores.length == 0) return 0;
            int count = 0;
            for(int i : scores){
                if(i == target)
                    count++;
            }
            return count;
        }
    }
    //双指针
    class Solution4 {
        public int search(int[] nums, int target) {
            int i = 0,j = nums.length-1;
            while(i<=j){
                if(nums[i]==nums[j] && nums[i]==target){
                    return j-i+1;
                }
                if(nums[i]<target){
                    i++;
                }
                if(nums[j]>target){
                    j--;
                }
            }
            return 0;
        }
    }
}
